The present invention is directed to extended greatest common divisor algorithms and in particular to improved extended binary and extended left-shift binary greatest common divisor algorithms that efficiently calculate arithmetic inverses over finite fields using tables of pre-computed values.
Modular arithmetic is used in many applications such as encryption algorithms and the generation of error correcting codes. When the modulus is a prime number (P), the operations of addition, subtraction, multiplication and division with nonzero elements as well as the associative, commutative and distributive properties are defined over the set of numbers from zero to p. This set of numbers defines a finite field modulo P, Fp. These fields are often referred to as “Prime Fields”.
Extended GCD algorithms are commonly used to find inverses in large finite fields, which are of interest for encryption purposes. As used herein, the term “extended” indicates that the GCD algorithm has been modified to calculate inverses. One type of encryption algorithm encrypts data using exponentiation over a large finite field, relying on the inherent difficulty of the inverse of exponentiation, the discrete logarithm problem, to hold the data secure. Encryption performed on a large finite field (having more elements) is more secure than encryption performed on a small field. One problem with using large finite fields, however, is the difficulty in performing even simple arithmetic operations on the large numbers in the field. Typical numbers used in data encryption have hundreds of bits. These numbers are too large to be easily handled by commonly available microprocessors that are limited to 32 or 64-bit arithmetic. This is especially true of exponentiation where a 100-bit number is raised to the power of second 100-bit number and the result is determined modulo a third 100-bit number. As described below, calculations using these large numbers are typically handled using multiprecision arithmetic.
Another type of encryption algorithm uses multiplication by an integer number within an elliptic curve group, where the group operation is symbolized by addition. (It is the analogous to exponentiation in groups, where the group operation is denoted by multiplication.) An elliptic curve group is defined on ordered pairs of points of a grid that lie on an elliptic curve defined by an equation such as equation (1)Y2=(X3+A·X+B) modulo P  (1)where P is a prime number equal to the number of rows and the number of columns in the grid together with a special point ◯, called the point at infinity. In elliptic curve cryptography, an encryption key is generated by multiplying a generator point P by itself k times. (i.e. Q=kP, where Q is the encryption key).
Multiplication by an integer in the elliptic curve group is modeled as repeated addition of the group elements to themselves. Addition of a group element to itself in an elliptic curve group, however, is not as simple as integer addition. Because points in the elliptic curve group are ordered pairs, addition may be represented as, (X1,Y1)+(X2,Y2)=(X3,Y3) where X3, Y3 are defined by equations (2) and (3) if neither of the points is the point at infinity (in which case the definition states that (X1,Y1)+◯=(X1,Y1)). L, a variable used in equations (2) and (3) is defined by equation (4).X3=L2−X1−X2 modulo P  (2)Y3=L(X1−X3)−Y1 modulo P  (3)L=(Y2−Y1)/(X2−X1) modulo P  (4)
If X1=X2 and Y1=Y2, X3 and Y3 are defined by equations (5) and (6).X3=L2−2X1 modulo P  (5)Y3=L(X1−X3)−Y1 modulo P  (6)L=(3X12+A)/2Y1  (7)Where A is the coefficient of X in equation (1).
Thus, addition of two members of the elliptic curve group involves a modular integer division operation. In modular arithmetic, division of a value N by a value D is often best handled as a multiplication of N by the arithmetic inverse of D, D−1. It is known that an arithmetic inverse of a number in a finite field may be calculated using an extended greatest common divisor (GCD) algorithm.
FIG. 1 is a flow chart diagram, which illustrates an extended version of the Binary GCD algorithm. The algorithm shown in FIG. 1 calculates the greatest common divisor of U and V where U is greater than V. The algorithm relies on the property that if U and V have a common divisor D so does U-V, U-2V and so on. Thus, using only subtraction and division by two (a binary right shift), one can calculate the GCD of U and V. In general, GCD algorithms operate by successively reducing the values of U and V while maintaining the equations (8), (9) and (10)U1U+U2·V=U3  (8)V1·U+V2·V=V3  (9)T1·U+T2V=T3  (10)where U≧V and (U1, U2, U3) and (V1, V2, V3) are initially assigned the values of (1, 0, U) and (0, 1, V), respectively. If the algorithm is used to calculate the greatest common divisor of a prime number P and a value X, then, upon termination, U3=GCD(P, X)=1 and U2=X−1 MOD P. In general terms, GCD algorithms operate by repetitively reducing the number of bits in the larger value, U, and switching the two values whenever U is less than V. Thus, the algorithm successively reduces the values of U3 and V3 while maintaining the equations. Because it also maintains the values U2 and V2, the algorithm shown in FIG. 1 not only calculates the greatest common divisor of U and V but also calculates V−1, the inverse of V modulo U (assuming U is a prime). Furthermore, it is noted that the variables U1, V1 and T1 do not need to be maintained because they can be determined from the other variables, for example, U1 can be determined from U2 and U3 by the identity U1=(U3−U2·V)/U. As described below, when U is a prime number, this inverse may be used for division operations performed on the Finite field FU.
The algorithm shown in FIG. 1 begins at step 110 by obtaining the values U and V and assigning the value of U to a temporary variable U3 and the value of V to a temporary variable V3. In the exemplary embodiment of the invention, the binary GCD process is used for encryption and U represents a large prime number, P.
Next, step 116 stores the current value of U3 into a temporary variable USAVE, sets a variable U2 to zero and sets a variable V2 to 1−USAVE. Next, step 122 is executed which assigns the value in V3 to a temporary variable T3, sets a temporary variable T2 to one and a temporary variable SIGN to zero.
After step 122, step 124 is executed which determines if T3 is even. If T3 is even the process performs a subtract and shift reduction. The first step in this reduction is step 126 which shifts T3 by one bit to less significant bit positions. In the exemplary processes shown in FIGS. 1, 2, 3 and 4, a shift operation toward less significant bits is a right-shift, and an operation which shifts a value x by y bit positions to the right is indicated by the function RS(x,y). After step 126, step 128 is executed which determines if T2 is even. If so, step 130 shifts T2 to less significant bit positions by one bit and transfers control to step 124, described above.
If T2 is odd at step 128, step 132 is executed which determines if T2 is greater than or equal to zero. If T2 is greater than or equal to zero, step 136 is executed which calculates the value T2−SAVE, shifts the value to less significant bit positions by one bit and assigns the result to T2. If, at step 132, T2 is less than zero, then step 134 calculates the value T2+USAVE, shifts the value to less significant bit positions by one bit and assigns the result to T2. After step 132 or step 134, control transfers to step 124, described above. The algorithm shown in FIG. 1 assumes that U is odd and, thus, that USAVE is odd. At step 132, T2 is odd. Either adding or subtracting two odd numbers produces an even number.
If T3 is odd at step 124, the algorithm performs a subtraction reduction process. The first step in this process, step 138, determines the value of the variable SIGN. If SIGN equals one, step 140 is executed which sets U3 to T3 and sets U2 to T2. Otherwise, step 142 is executed which sets V3 to T3 and V2 to T2. After step 140 or 142, step 144 is executed which compares U3 and V3. If U3 is greater than V3, then step 146 is executed which sets SIGN to one, sets T3 to U3 minus V3 and sets T2 to U2 minus V2. If U3 is not greater than V3 at step 144, then step 148 is executed which sets SIGN to zero, sets T3 to V3 minus U3 and sets T2 to V2 minus U2. After step 146 or step 148, step 150 is executed which tests the value in T3 to determine if the GCD process is done. If T3 equals zero then the process is done and step 152 is executed which returns U3 and U2. Because, in the exemplary embodiment, U is prime, U3 is equal to one and U2 equals V−1 modulo U.
The reduction step for exemplary binary GCD algorithm performs a single subtraction and a single shift operation during each reduction step. While this algorithm, because it uses only addition, subtraction and shifting, may be implemented using only relatively simple hardware it typically uses many iterations to find the GCD and, thus, the inverse of numbers typically used in cryptography.